Mật mã

Số nguyên tố p = 2 ⋅ q + 1 {\displaystyle p=2\cdot q+1} được gọi là số nguyên tố an toàn nếu như q là số nguyên tố. Do đó p = 2 ⋅ q + 1 {\displaystyle p=2\cdot q+1} là số nguyên tố an toàn khi và chi khi q là số nguyên tố Sophie Germain, do vậy việc tìm ra các số nguyên tố an toàn và việc tìm số Sophie Germain có độ khó tính toán tương đương nhau. Khái niệm số nguyên tố an toàn có thể trở thành số nguyên tố mạnh khi cả p + 1 {\displaystyle p+1} và p − 1 {\displaystyle p-1} đều có các thừa số nguyên tố đủ lớn. Các số nguyên tố an toàn và mạnh có tính hữu dụng trong việc là thừa số của khóa bí mật trong hệ mã hóa RSA, do chúng ngăn chặn việc phá hệ mã hóa bằng các giải thuật phân tích thừa số nguyên tố đã biết như giải thuật Pollard được áp dụng cho các khóa bí mật không phải là số nguyên tố mạnh.[18]

Các vấn đề tương tự cũng được áp dụng cho các hệ mã hóa khác bao gồm trao đổi khóa Diffie–Hellman và các hệ tương đương có độ an toàn phụ thuộc vào độ khó của bài toán Lôgarit rời rạc hơn là việc phân tích thừa số số nguyên.[19] Vì lý do này mà các giao thức tạo khóa cho các phương pháp này thường dựa trên các giải thuật hiệu quả trong việc tạo các số nguyên tố mạnh, mà các giải thuật đó lại dựa trên dự đoán rằng các số nguyên tố này có mật độ đủ lớn.[20]

Trong chế độ mã hóa Sophie Germain Counter, người ta đề xuất sử dụng các giải thuật trong trường hữa hạn có cấp bằng với số nguyên tố Sophie Germain 2 128 + 12451 {\displaystyle 2^{128}+12451} để khắc phục nhược điểm trong chế độ mã hóa Galois/Counter Mode sử dụng trường hữu hạn nhị phân GF(2128). Tuy nhiên SGCM được chứng minh rằng có cùng điểm yếu trong nhiều tấn công mã hóa tương tự GCM.[21]

Kiểm tra tính nguyên tố

Trong phiên bản đầu tiên của nghiên cứu phép kiểm tra tính nguyên tố AKS, một dự đoán về số nguyên tố Sophie Germain được sử dụng để giảm độ phức tạp của trường hợp xấu nhất từ O(log12n) giảm thành O(log6n). Phiên bản sau của nghiên cứu được chứng minh rằng có độ phức tạp thời gian O(log7.5n) mà cũng có thể giảm thành O(log6n).[22] Những biến thể sau này của AKS đã chứng minh có độ phức tạp thời gianO(log6n) mà không cần bất kỳ dự đoán nào hay là sử dụng số nguyên tố Sophie Germain.

Tạo số giả ngẫu nhiên

Có thể sử dụng số nguyên tố Sophie Germain để tạo các số giả ngẫu nhiên. Mở rộng thập phân của 1/q sẽ sinh ra dòng q − 1 {\displaystyle q-1} chữ số giả ngẫu nhiên nếu q là số nguyên tố an toàn của số Sophie Germain p, trong đó p đồng dư 3, 9, hoặc 11 (mod 20).[23] Do đó các số nguyên tố q "phù hợp" là 7, 23, 47, 59, 167, 179, vân vân. ( A000353) (tương ứng với p = 3 , 11 , 23 , 29 , 83 , 89 {\displaystyle p=3,11,23,29,83,89} ; vân vân.) ( A000355). Kết quả là dòng chữ số dài q − 1 {\displaystyle q-1} (tính luôn các số 0 ở trước). Ví dụ, với q = 23 ta tạo được các con số giả ngẫu nhiên 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3. Chú ý rằng không phù hợp với mục đích mã hóa do giá trị của mỗi số có thể được dự đoán từ giá trị đứng trước trong chuỗi số.